{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Nearest Exit from Entrance in Maze"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nearestExit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #迷宫中离入口最近的出口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m x n</code> 的迷宫矩阵 <code>maze</code> （<strong>下标从 0 开始</strong>），矩阵中有空格子（用 <code>'.'</code> 表示）和墙（用 <code>'+'</code> 表示）。同时给你迷宫的入口 <code>entrance</code> ，用 <code>entrance = [entrance<sub>row</sub>, entrance<sub>col</sub>]</code> 表示你一开始所在格子的行和列。</p>\n",
    "\n",
    "<p>每一步操作，你可以往 <strong>上</strong>，<strong>下</strong>，<strong>左</strong> 或者 <strong>右</strong> 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 <code>entrance</code> <strong>最近</strong> 的出口。<strong>出口</strong> 的含义是 <code>maze</code> <strong>边界</strong> 上的 <strong>空格子</strong>。<code>entrance</code> 格子 <strong>不算</strong> 出口。</p>\n",
    "\n",
    "<p>请你返回从 <code>entrance</code> 到最近出口的最短路径的 <strong>步数</strong> ，如果不存在这样的路径，请你返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/04/nearest1-grid.jpg\" style=\"width: 333px; height: 253px;\">\n",
    "<pre><b>输入：</b>maze = [[\"+\",\"+\",\".\",\"+\"],[\".\",\".\",\".\",\"+\"],[\"+\",\"+\",\"+\",\".\"]], entrance = [1,2]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。\n",
    "一开始，你在入口格子 (1,2) 处。\n",
    "- 你可以往左移动 2 步到达 (1,0) 。\n",
    "- 你可以往上移动 1 步到达 (0,2) 。\n",
    "从入口处没法到达 (2,3) 。\n",
    "所以，最近的出口是 (0,2) ，距离为 1 步。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/04/nearesr2-grid.jpg\" style=\"width: 253px; height: 253px;\">\n",
    "<pre><b>输入：</b>maze = [[\"+\",\"+\",\"+\"],[\".\",\".\",\".\"],[\"+\",\"+\",\"+\"]], entrance = [1,0]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>迷宫中只有 1 个出口，在 (1,2) 处。\n",
    "(1,0) 不算出口，因为它是入口格子。\n",
    "初始时，你在入口与格子 (1,0) 处。\n",
    "- 你可以往右移动 2 步到达 (1,2) 处。\n",
    "所以，最近的出口为 (1,2) ，距离为 2 步。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/04/nearest3-grid.jpg\" style=\"width: 173px; height: 93px;\">\n",
    "<pre><b>输入：</b>maze = [[\".\",\"+\"]], entrance = [0,0]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>这个迷宫中没有出口。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>maze.length == m</code></li>\n",
    "\t<li><code>maze[i].length == n</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 100</code></li>\n",
    "\t<li><code>maze[i][j]</code> 要么是 <code>'.'</code> ，要么是 <code>'+'</code> 。</li>\n",
    "\t<li><code>entrance.length == 2</code></li>\n",
    "\t<li><code>0 &lt;= entrance<sub>row</sub> &lt; m</code></li>\n",
    "\t<li><code>0 &lt;= entrance<sub>col</sub> &lt; n</code></li>\n",
    "\t<li><code>entrance</code> 一定是空格子。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [nearest-exit-from-entrance-in-maze](https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [nearest-exit-from-entrance-in-maze](https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"+\",\"+\",\".\",\"+\"],[\".\",\".\",\".\",\"+\"],[\"+\",\"+\",\"+\",\".\"]]\\n[1,2]', '[[\"+\",\"+\",\"+\"],[\".\",\".\",\".\"],[\"+\",\"+\",\"+\"]]\\n[1,0]', '[[\".\",\"+\"]]\\n[0,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        rows, cols = len(maze), len(maze[0])\n",
    "        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))\n",
    "        \n",
    "        # Mark the entrance as visited since its not a exit.\n",
    "        start_row, start_col = entrance\n",
    "        maze[start_row][start_col] = \"+\"\n",
    "        \n",
    "        # Start BFS from the entrance, and use a queue `queue` to store all \n",
    "        # the cells to be visited.\n",
    "        queue = collections.deque()\n",
    "        queue.append([start_row, start_col, 0])\n",
    "        \n",
    "        while queue:\n",
    "            curr_row, curr_col, curr_distance = queue.popleft()\n",
    "            \n",
    "            # For the current cell, check its four neighbor cells.\n",
    "            for d in dirs:\n",
    "                next_row = curr_row + d[0]\n",
    "                next_col = curr_col + d[1]\n",
    "                \n",
    "                # If there exists an unvisited empty neighbor:\n",
    "                if 0 <= next_row < rows and 0 <= next_col < cols \\\n",
    "                    and maze[next_row][next_col] == \".\":\n",
    "                    \n",
    "                    # If this empty cell is an exit, return distance + 1.\n",
    "                    if 0 == next_row or next_row == rows - 1 or 0 == next_col or next_col == cols - 1:\n",
    "                        return curr_distance + 1\n",
    "                    \n",
    "                    # Otherwise, add this cell to 'queue' and mark it as visited.\n",
    "                    maze[next_row][next_col] = \"+\"\n",
    "                    queue.append([next_row, next_col, curr_distance + 1])\n",
    "            \n",
    "        # If we finish iterating without finding an exit, return -1.\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        queue = deque()\n",
    "        queue.append(entrance)\n",
    "        count = 0\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        maze[entrance[0]][entrance[1]] = '+'\n",
    "        while queue:\n",
    "            count += 1\n",
    "            for i in range(len(queue)):\n",
    "                x, y = queue.popleft()\n",
    "                for new_x, new_y in ((x+1, y), (x-1, y), (x, y-1), (x, y+1)):\n",
    "                    if 0 <= new_x < m and 0 <= new_y < n and maze[new_x][new_y] != '+':\n",
    "                        if new_x in (0, m-1) or new_y in (0, n-1):\n",
    "                            return count\n",
    "                        maze[new_x][new_y] = '+'\n",
    "                        queue.append([new_x, new_y])\n",
    "        return -1\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        # 上下左右四个相邻坐标对应的行列变化量\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        # 入口加入队列并修改为墙\n",
    "        q = deque([(entrance[0], entrance[1], 0)])\n",
    "        maze[entrance[0]][entrance[1]] = '+'\n",
    "        while q:\n",
    "            cx, cy, d = q.popleft()\n",
    "            # 遍历四个方向相邻坐标\n",
    "            for k in range(4):\n",
    "                nx = cx + dx[k]\n",
    "                ny = cy + dy[k]\n",
    "                if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == '.':\n",
    "                    # 新坐标合法且不为墙\n",
    "                    if nx == 0 or nx == m - 1 or ny == 0 or ny == n - 1:\n",
    "                        # 新坐标为出口，返回距离作为答案\n",
    "                        return d + 1\n",
    "                    # 新坐标为空格子且不为出口，修改为墙并加入队列\n",
    "                    maze[nx][ny] = '+'\n",
    "                    q.append((nx, ny, d + 1))\n",
    "        # 不存在到出口的路径，返回 -1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        queue = collections.deque([[entrance,0]])\n",
    "        m,n=len(maze),len(maze[0])\n",
    "        while queue:\n",
    "            (i,j),d = queue.popleft()\n",
    "            for x,y in [(i+1,j),(i,j-1),(i,j+1),(i-1,j)]:\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    if maze[x][y]==\".\":\n",
    "                        maze[x][y]='+'\n",
    "                        queue.append([(x,y),d+1])\n",
    "                else:\n",
    "                    if [i,j]!=entrance:\n",
    "                        return d\n",
    "        return -1\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        # 上下左右四个相邻坐标对应的行列变化量\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        # 入口加入队列并修改为墙\n",
    "        q = deque([(entrance[0], entrance[1], 0)])\n",
    "        maze[entrance[0]][entrance[1]] = '+'\n",
    "        while q:\n",
    "            cx, cy, d = q.popleft()\n",
    "            # 遍历四个方向相邻坐标\n",
    "            for k in range(4):\n",
    "                nx = cx + dx[k]\n",
    "                ny = cy + dy[k]\n",
    "                if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == '.':\n",
    "                    # 新坐标合法且不为墙\n",
    "                    if nx == 0 or nx == m - 1 or ny == 0 or ny == n - 1:\n",
    "                        # 新坐标为出口，返回距离作为答案\n",
    "                        return d + 1\n",
    "                    # 新坐标为空格子且不为出口，修改为墙并加入队列\n",
    "                    maze[nx][ny] = '+'\n",
    "                    q.append((nx, ny, d + 1))\n",
    "        # 不存在到出口的路径，返回 -1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        # 因为要求的是找出的是最近的出口， 因此广度优先遍历符合要求，因为每次遍历一遍\n",
    "        # 相当于走一遍最近一步的所有可能\n",
    "        # 如何防止重复行走 使用一个存储当前路径的数组？这样时间复杂度会在原来的基础上乘n\n",
    "        # 官方题解使用的方法是将所有遍历过的数组都更改为\"+\"，当出队时是否需要进行更改\n",
    "        # 应该不需要\n",
    "        \n",
    "        # 使用collections.deque\n",
    "        # 判断是否在边界， 如果在边界，那么直接返回\n",
    "        que = collections.deque()\n",
    "        entrance.append(0)  # 插入一个0， 标记当前的步数\n",
    "        que.append(entrance)\n",
    "        n = len(maze)\n",
    "        m = len(maze[0])\n",
    "        while que:\n",
    "            x, y, deep = que.popleft()\n",
    "            if (x - 1 < 0 or x + 1 >= n or y - 1 < 0 or y + 1 >= m) and ([x, y] != entrance[0:2]):\n",
    "                return deep\n",
    "\n",
    "            if x - 1 >= 0 and maze[x - 1][y] != '+':  # 左边\n",
    "                que.append((x - 1, y, deep + 1))\n",
    "                maze[x - 1][y] = '+'\n",
    "            if x + 1 < n and maze[x + 1][y] != '+':\n",
    "                que.append((x + 1, y, deep + 1))\n",
    "                maze[x + 1][y] = '+'\n",
    "            if y - 1 >= 0 and maze[x][y - 1] != '+':\n",
    "                que.append((x, y - 1, deep + 1))\n",
    "                maze[x][y - 1] = '+'\n",
    "            if y + 1 < m and maze[x][y + 1] != '+':\n",
    "                que.append((x, y + 1, deep + 1))\n",
    "                maze[x][y + 1] = '+'\n",
    "        return -1\n",
    "\n",
    "                \n",
    "                    \n",
    "\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        queue = []\n",
    "        queue.append(entrance)\n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "        d = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        maze[entrance[0]][entrance[1]] = '+'\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            l = len(queue)\n",
    "            for i in range(l):\n",
    "                cur = queue.pop(0)\n",
    "                for j in range(4):\n",
    "                    nx, ny = cur[0] + d[j][0], cur[1] + d[j][1]\n",
    "                    if nx < 0 or nx >= m or ny < 0 or ny >= n or maze[nx][ny] == '+':\n",
    "                        continue\n",
    "                    if nx == 0 or nx == m - 1 or ny == 0 or ny == n - 1:\n",
    "                        return ans + 1\n",
    "                    maze[nx][ny] = '+'\n",
    "                    queue.append([nx, ny])\n",
    "            ans += 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:   \n",
    "        m = len(maze)\n",
    "        n = len(maze[0])\n",
    "        result = [[-1 for j in range(n)] for i in range(m)]\n",
    "        vx = [-1, 1, 0, 0]\n",
    "        vy = [0, 0, -1, 1]\n",
    "        q = [[entrance[0], entrance[1], 0]]\n",
    "        left = 0\n",
    "        right = 0\n",
    "        result[entrance[0]][entrance[1]] = 0\n",
    "        while left <= right:\n",
    "            cur = q[left]\n",
    "            if (cur[0] == 0 or cur[0] == m - 1 or cur[1] == 0 or cur[1] == n - 1) and cur[2] != 0:\n",
    "                return cur[2]\n",
    "            for i in range(4):\n",
    "                tx = cur[0] + vx[i]\n",
    "                ty = cur[1] + vy[i]\n",
    "                if tx >= 0 and tx < m and ty >= 0 and ty < n:\n",
    "                    if maze[tx][ty] == \".\" and result[tx][ty] == -1:\n",
    "                        right += 1\n",
    "                        result[tx][ty] = cur[2] + 1\n",
    "                        q.append([tx, ty, cur[2] + 1])\n",
    "            left += 1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        m=len(maze)\n",
    "        n=len(maze[0])\n",
    "        q=[]\n",
    "        for x in [0,m-1]:\n",
    "            for y in range(n):\n",
    "                if maze[x][y]=='.'and [x,y]!=entrance:\n",
    "                    maze[x][y]='+'\n",
    "                    q.append([x,y])\n",
    "        for y in [0,n-1]:\n",
    "            for x in range(m):\n",
    "                if maze[x][y]=='.' and [x,y]!=entrance:\n",
    "                    maze[x][y]='+'\n",
    "                    q.append([x,y])\n",
    "      \n",
    "      \n",
    "        step=0\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                x,y=q.pop()\n",
    "                if [x,y]==entrance:\n",
    "                    return step\n",
    "        \n",
    "                for xn,yn in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:\n",
    "                    if 0<=xn<m and 0<=yn<n and maze[xn][yn]=='.':\n",
    "                        q.insert(0,[xn,yn])\n",
    "                        maze[xn][yn]='+'\n",
    "            step+=1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        m,n = len(maze),len(maze[0])\n",
    "        dix = [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "        queue = collections.deque([entrance])\n",
    "        x,y = entrance\n",
    "        maze[x][y] = '+'\n",
    "        count = 1\n",
    "        while queue:\n",
    "            tmp = queue\n",
    "            queue = []\n",
    "            for x,y in tmp:\n",
    "                for dx,dy in dix:\n",
    "                    if m > x+dx>=0<=y+dy<n and maze[x+dx][y+dy] == '.':\n",
    "                        if x + dx in [0,m-1] or y+dy in [0,n-1]:\n",
    "                            return count\n",
    "                        maze[x+dx][y+dy] = '+'\n",
    "                        queue.append([x+dx,y+dy])\n",
    "            count += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        exitlist = list()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (maze[i][j] == \".\" and (i == 0 or j == 0 or i == m-1 or j == n-1)):\n",
    "                    exitlist.append((i,j))\n",
    "        \n",
    "        q = collections.deque([(entrance[0], entrance[1], 0)])\n",
    "        maze[entrance[0]][entrance[1]] = \"+\"\n",
    "        \n",
    "        while len(q) > 0:\n",
    "            x, y, d = q.popleft()\n",
    "            for nxt, nyt in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:\n",
    "                if ((0 <= nxt < m and 0 <= nyt < n ) and maze[nxt][nyt] == \".\" ):\n",
    "                    if (nxt,nyt) in exitlist:\n",
    "                        return d+1\n",
    "                         \n",
    "                    q.append((nxt, nyt, d+1))\n",
    "                    maze[nxt][nyt] = \"+\"        \n",
    "        return -1 \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        queue = collections.deque()\n",
    "        queue.append((entrance[0], entrance[1]))\n",
    "        maze[entrance[0]][entrance[1]] = '+'\n",
    "        cnt = -1\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            cnt += 1\n",
    "            for _ in range(size):\n",
    "                i, j = queue.popleft()\n",
    "                if cnt >=1 and (i== 0 or i == m-1 or j == 0 or j == n-1):\n",
    "                    return cnt\n",
    "                if i-1 >= 0 and maze[i-1][j] =='.':\n",
    "                    queue.append((i-1,j))\n",
    "                    maze[i-1][j] = '+'\n",
    "                if i+1 < m and maze[i+1][j] =='.':\n",
    "                    queue.append((i+1,j))\n",
    "                    maze[i+1][j] = '+'\n",
    "                if j-1 >= 0 and maze[i][j-1] =='.':\n",
    "                    queue.append((i,j-1))\n",
    "                    maze[i][j-1] = '+'\n",
    "                if j+1 < n and maze[i][j+1] =='.':\n",
    "                    queue.append((i,j+1))\n",
    "                    maze[i][j+1] = '+'\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isExit(self,maze,grid,m,n):\n",
    "        if (grid[0]==0 or grid[0]==m-1 or grid[1]==0 or grid[1]==n-1) and maze[grid[0]][grid[1]] == '.':\n",
    "            return True \n",
    "        else:\n",
    "            return False       \n",
    "\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        m,n = len(maze),len(maze[0])\n",
    "        q = []\n",
    "        q.append(entrance)\n",
    "        visited = {(entrance[0],entrance[1])}\n",
    "        ans = 0\n",
    "        flag = 0\n",
    "\n",
    "        while q and flag!=1:\n",
    "            ans += 1\n",
    "            for _ in range(len(q)):               \n",
    "                grid = q.pop(0)\n",
    "                x,y = grid[0], grid[1]\n",
    "                for i,j in zip([0,0,1,-1],[1,-1,0,0]):\n",
    "                    new_x,new_y = x+i,y+j\n",
    "                    if 0<=new_x<m and 0<=new_y<n and (new_x,new_y) not in visited:\n",
    "                        if self.isExit(maze,[new_x,new_y],m,n):\n",
    "                            flag = 1\n",
    "                            break\n",
    "                        elif maze[new_x][new_y] == '.':\n",
    "                            q.append([new_x,new_y])\n",
    "                            visited.add((new_x,new_y))\n",
    "                if flag==1:\n",
    "                    break\n",
    "                \n",
    "        if flag:\n",
    "            return ans\n",
    "        return -1\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n",
    "        m, n = len(maze), len(maze[0])\n",
    "        x, y = entrance\n",
    "\n",
    "        visited = set()\n",
    "        q = deque()\n",
    "        q.append(((x, y), 0))\n",
    "        while q:\n",
    "            (x, y), d = q.popleft()\n",
    "            if x == 0 or x == m - 1 or y == 0 or y == n - 1:\n",
    "                if [x, y] != entrance:\n",
    "                    return d\n",
    "            if (x, y) not in visited:\n",
    "                visited.add((x, y))\n",
    "                for nx, ny in ((x-1,y),(x+1,y),(x,y-1),(x,y+1)):\n",
    "                    if 0 <= nx < m and 0 <= ny < n:\n",
    "                        if maze[nx][ny] == \".\":\n",
    "                            q.append(((nx, ny), d + 1))\n",
    "                        \n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
